#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    // void traceback(vector<vector<int>> &res, vector<int> &path, map<int, int> &flag,
    //                int sum, int k, int n)
    // {
    //     if (sum > n || (int)(path.size()) > k)
    //     {
    //         return;
    //     }
    //     if (sum == n && (int)(path.size()) == k)
    //     {
    //         vector<int> temp = path;
    //         sort(temp.begin(), temp.end());
    //         if (res.empty())
    //         {
    //             res.push_back(path);
    //         }
    //         else
    //         {
    //             for (auto vec : res)
    //             {
    //                 if (vec == temp)
    //                 {
    //                     return;
    //                 }
    //             }
    //             res.push_back(path);
    //         }
    //     }
    //     for (int i = 1; i <= 9; i++)
    //     {
    //         if (flag[i] == 1)
    //         {
    //             continue;
    //         }
    //         else
    //         {
    //             sum += i;
    //             path.push_back(i);
    //             flag[i] = 1;
    //             traceback(res, path, flag, sum, k, n);
    //             flag[i] = 0;
    //             path.pop_back();
    //             sum -= i;
    //         }
    //     }
    // }
    // vector<vector<int>> combinationSum3(int k, int n)
    // {
    //     vector<vector<int>> res;
    //     vector<int> path;
    //     map<int, int> flag;
    //     for (int i = 1; i <= 9; i++)
    //     {
    //         flag[i] = 0;
    //     }
    //     int sum = 0;
    //     traceback(res, path, flag, sum, k, n);
    //     return res;
    // }

    void traceback(vector<vector<int>> &res, vector<int> &path, int sum, int k, int n, int start)
    {
        if (sum > n)
        {
            return;
        }
        if ((int)path.size() == k)
        {
            if (sum == n)
            {
                res.push_back(path);
            }
        }
        for (int i = start; i <= 9 - (k - (int)path.size()) + 1; i++)
        {
            sum += i;
            path.push_back(i);
            traceback(res, path, sum, k, n, i + 1);
            path.pop_back();
            sum -= i;
        }
    }
    vector<vector<int>> combinationSum3(int k, int n)
    {
        vector<vector<int>> res;
        vector<int> path;
        traceback(res, path, 0, k, n, 1);
        return res;
    }
};

int main()
{
    Solution sol;
    vector<vector<int>> res = sol.combinationSum3(3, 7);
    for (auto vec : res)
    {
        for (auto num : vec)
        {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}